#include <iostream>
using namespace std;

/*
//2012.4.25
//寻找一个串里的最长递增子串  22号时参加微软的实习笔试这个题没做出来
//第一种思路是先把这个子串排序，然后再比较排序后的串，跟原串的最长公共子串（LCS算法），复杂度好像有O(nlgn + n*n)
//第二种思路是算出来以每个a[i]结尾的最长递增子串有多长，然后再增加a[i+1]进去考虑。增加去考虑时，把以a[1],a[2],a[3]....a[i]
//结尾的最长递增子串都要考虑，看a[i+1]能够加在哪个后面。如果都不能加，则以a[i+1]结尾的最长递增子串长度就是它本身，为1，否则把
//原来的最长递增子串的长度加1. 然后从N个求得的最长递增子串中找出长度最长的。
//但是：在寻找a[i+1]之前的最长递增子串时，也是有两种方法，一种是顺序查找，复杂度为o(i)，另外一种是用二分查找，复杂度O（lgi)，从而
//降低整个的复杂度。
http://www.cnblogs.com/chenleiustc/archive/2009/04/14/1435577.html
*/

int a[10] = {8,6,3,4,11,0,9,5,9,10};


// Find the longest sub sequence in O(n) time!
int getLongestIncSubSeq_N(int a[], int lenA, int b[], int pos)
{
    int max = 0;
    for (int i=0; i<pos; i++)
    {
        if (a[i] < a[pos] && b[i] > max)          // <  --> strictly increasing!!!!
            max  = b[i];
    }
    return max + 1;
}


// Better algorithm to find the longest sub sequence in O(lg(n)) time!!!!
//实现方法是，用另外一个数组c[]，代替b[]的作用。采用不同的策略来保存到c[]中。
//比如c[2]就表示最长递增串为2时的那个子串的结尾的元素，
//**注意有一个重要性质就是C中的元素一定是递增的,保证这个性质的前提是，如果有几个数都可以放在c[i]中，c[i]中应保存最小的那个
//**花了好长的时间才完全写对这个算法！！！  得非常非常细心才能不出错！！！

#define UNPROCESSED  0xFFFFFFFF
int getLongestIncSubSeq_LOGN(int c[], int len, int num)
{
    int left, mid, right;

    if (len < 1)
        return 0;
    left = 0;
    right = len - 1;
    mid = (left + right) / 2;
    while (left <= right)  // = 号非常重要！否则会遗漏情况
    {
        if (c[mid] > num || c[mid] == UNPROCESSED)
        {
            right = mid-1;
            mid = (left + right)/2;
        }
        else if (c[mid] == num && c[mid] != UNPROCESSED)
        {
            return mid;
        }
        else
        {
            left = mid+1;
            mid = (left + right )/2;
        }
    }
    //cout<<"here"<<left<<mid<<right<<" ";//test
    // cout<<","<<left<<","<<"  "; //test
    //for(int i=0; i<10; i++)
    //    cout<<c[i]<<",";
    //cout<<":"<<num<<endl;
    return left;
}

int method_O_N()
{
    int b[10] ;     //b[i] is the length of the max LIS which ends with a[i]

    //First get all the values of b[i]
    int i;
    b[0] = 1;
    for (i=1; i<10; i++)
    {
        b[i] = getLongestIncSubSeq_N(a, 10, b,i);
    }

    //Then find the greatest b[i] among b[]
    int max = 0;
    for (i=0; i<10; i++)
    {
        if (b[i] > max)
        {
            max = b[i];
        }
    }
    cout<<"Result of method_O_N:"<<max<<endl;
}

int method_O_LOGN()
{
    int c[10] ;     //c[i]是长度为i的递增子串的末尾元素。如果有多个，则取小的一个。 由于数组从0开始，所以最后要+1

    //First get all the values of b[i]
    int i;
    for (i=0; i<10; i++)
    {
        c[i] = UNPROCESSED;
    }
    c[0] = a[0]; //实际上是长度为1，不过数组从0开始，所以这里就先不管，到最后再+1
    for (i=1; i<10; i++)
    {
        int maxLenSoFar =  getLongestIncSubSeq_LOGN(c, i+1, a[i]) ;
        if (c[maxLenSoFar] == UNPROCESSED || c[maxLenSoFar] > a[i])  //返回的这个位置，还没有保存过元素，或者保存的并不是最小的
        {
            c[maxLenSoFar] = a[i];
        }
//        if (c[maxLenSoFar] < a[i] && (c[maxLenSoFar + 1] > a[i] || c[maxLenSoFar+1] == -1))
        //          c[maxLenSoFar + 1] = a[i];
    }

    //Then find the greatest b[i] among b[]
    int max = 0;
    for(i=0; i<10; i++)
    {
        if(c[i] != -1)
            max = i;
    }
    max = max + 1;  //因为数组下标是从0开始的
    cout<<"Result of method_O_LogN:"<<max<<endl;
}

int main()
{
    method_O_N();
    method_O_LOGN();
}

